/*!  数据结构向量 
 *  
 * @author 周鑫
 * @date 2021.9.14 
 */
#pragma once
#include <algorithm>
#include <iostream>
#include <ostream>
const int DEFAULT_CAPACITY=10;

using T=int;

using Rank =int;
class Vector
{

public:
//* 只读访问接口
    int & operator[](Rank r) const{return _elem[r];}//寻秩访问//? 为什么返回地址
    Rank find(int const &e, Rank lo, Rank hi);//顺序查找//todo 其他版本待实现
    int size(){return _size;}
//* 可写访问接口
    Rank insert(Rank r, int const &e);
    int remove(Rank lo, Rank hi);//区间删除
    int remove(Rank r){int e=_elem[r]; remove(r,r+1); return e;}//单元素删除
    int deduplicate();//去重
//* 遍历
    void traverse(void(* visit)(int &)){
        for(int i=0;i<_size;i++) visit(_elem[i]);//? 为什么visit不用加*号
    }
    template <typename VST>
    void traverse(VST visit){
        for(int i=0;i<_size;i++) visit(_elem[i]);
    }

//* 构造函数
    Vector(): _size(0), _capacity(DEFAULT_CAPACITY){_elem=new int[_capacity];}                            //默认构造
    Vector(int const *A, Rank lo, Rank hi):_size(hi-lo),_capacity(std::max((hi-lo)*2,DEFAULT_CAPACITY)){copyFrom(A, lo,hi);} //todo 拷贝构造
    ~Vector(){delete[] _elem;}
//* 排序
    void sort(int k){
        switch (k)
        {
        case 0:
            bubbleSort(0,_size);
            std::cout<<"冒泡排序"<<std::endl;
            break;
        case 1:
            mergeSort(0, _size);
            std::cout<<"归并排序"<<std::endl;
            break;
        
        default:
            break;
        }
    }


protected:
    void copyFrom(int const *A, Rank lo, Rank hi);
    void bubbleSort(Rank,Rank);
    void expand(); //扩容
    void merge(Rank, Rank, Rank);
    void mergeSort(Rank ,Rank);
private:
    int *_elem;
    int _capacity;
    int _size;
};


